吊打XXX

Time Limit: 10 Sec Memory Limit: 128 MB

Description

gty又虐了一场比赛，被虐的蒟蒻们决定吊打gty。
　　gty见大势不好机智的分出了n个分身，但还是被人多势众的蒟蒻抓住了。
　　蒟蒻们将n个gty吊在n根绳子上，每根绳子穿过天台的一个洞。这n根绳子有一个公共的绳结x。
　　吊好gty后蒟蒻们发现由于每个gty重力不同，绳结x在移动。
　　蒟蒻wangxz脑洞大开的决定计算出x最后停留处的坐标，由于他太弱了决定向你求助。
　　不计摩擦，不计能量损失，由于gty足够矮所以不会掉到地上。

Input

输入第一行为一个正整数n，表示gty的数目。
　　接下来n行,每行三个整数xi，yi，wi，表示第i个gty的横坐标，纵坐标和重力。
　　对于20%的数据，gty排列成一条直线。

Output

输出1行两个浮点数（保留到小数点后3位），表示最终x的横、纵坐标。

Sample Input

3
　0 0 1
　0 2 1
　1 1 1

Sample Output

0.577 1.000

HINT

对于50%的数据，1<=n<=1000。
　　对于100%的数据，1<=n<=10000,-100000<=xi,yi<=100000

Main idea

求一个坐标，使得整个坐标到其余点的dist*val最小。

Solution

我们看到这种数据，显然使用模拟退火即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include<bits/stdc++.h>
using namespace std;
typedef long long s64;

const int ONE = 10005;
const int INF = 2147483640;

int n;
double Ans_min = 1.0*1e18;
double T;

struct power
{
    double x,y;
    double val;
}a[ONE],Now,Ans,A;

int get()
{
    int res=1,Q=1;    char c;
    while( (c=getchar())<48 || c>57)
        if(c=='-')Q=-1;
    if(Q) res=c-48;
    while((c=getchar())>=48 && c<=57)
        res=res*10+c-48;
    return res*Q;
}

double dist(power a,power b)
{
    return sqrt( (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y) );
}

double Judge(power Now)
{
    double res=0;
    for(int i=1;i<=n;i++)
        res+= a[i].val * dist(Now,a[i]);
    if(res < Ans_min) Ans_min = res, Ans = Now;
    return res;
}

double Random() {return (double)rand()/RAND_MAX;}
void SA(double T)
{
    Now = Ans;
    while(T > 0.001)
    {
        A.x = Now.x + T*(Random() * 2 -1);
        A.y = Now.y + T*(Random() * 2 -1);
        double dE = Judge(Now) - Judge(A);
        if(dE > 0 || Random() <= exp(dE/T))
            Now = A;
        T *= 0.98;
    }
    for(int i=1; i<=1000; i++)
    {
        A.x = Ans.x + T*(Random() * 2 - 1);
        A.y = Ans.y + T*(Random() * 2 - 1);
        Judge(A);
    }
}

int main()
{
    n=get();
    for(int i=1;i<=n;i++)
    {
        a[i].x=get();   a[i].y=get();   a[i].val=get();
        Ans.x += a[i].x;    Ans.y += a[i].y;
    }
    Ans.x/=n;   Ans.y/=n;

    SA(1000001);

    printf("%.3lf %.3lf",Ans.x,Ans.y);
}